package sk.fiit.lulco.grafy;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

import sk.fiit.lulco.grafy.HEALConstants.SortType;
/**
 * class for hybrid evolution algorithm Lulco
 */
public class HEALAlgorighm extends AbstractAlgorithm {

	private static double PERMUTATION_PROBABILITY = 0.25;
//	private static double CROSS_PROBABILITY = 0.25;
	private static double CONFLICTED_VERTICES_MUTATION_PROBABILITY = 0.90;
	private static double NON_CONFLICTED_VERTICES_MUTATION_PROBABILITY = 0.10;
	private static double CROSS_PORTION = 0.05;
	private static int GENERATIONS_COUNT = 100;
	private static int INDIVIDUALS_IN_GENERATION = 100;
	private static double NEW_GENERATION_RANDOM_INDIVIDUALS = 0.1;
	private static final VertexConflictsComparator vertexConflictsComparator = new VertexConflictsComparator(SortType.DESC);
	/**
	 * method for coloring
	 * 
	 * @param	Graph	graph
	 * @return	Graph
	 */
	public Graph color(Graph graph) {
		Graph bestIndividual = null;
		RandomColoringAlgorithm randomColoring = new RandomColoringAlgorithm();
		BrelazAlgorithm brelaz = new BrelazAlgorithm();
		List<Graph> generation = new ArrayList<Graph>();
		List<Graph> nextGeneration = new ArrayList<Graph>();
		
		graph = brelaz.color(graph);
		graph.setBestColoring(graph.getColors(null).size());
		
		// TODO 10 % bude uz ofarbenych brelazom, 10 %
		for (int i = 0; i < 10; i++) {
			Graph newGraph = new Graph(graph);
			nextGeneration.add(newGraph);
		}

		int generationBase = (int)((1 - NEW_GENERATION_RANDOM_INDIVIDUALS) * INDIVIDUALS_IN_GENERATION);
		int generationAdded = INDIVIDUALS_IN_GENERATION - generationBase;
		for (int i = 0; i < generationBase; i++) {
			Graph newGraph = new Graph(graph.getMatrix(), graph.getChromaticNumber(), graph.getBestColoring(), graph.getInitialColors());
			nextGeneration.add(randomColoring.color(newGraph));
		}
	
		for (int j = 0; j < GENERATIONS_COUNT; j++) {
			System.out.println("generation: " + j);
			for (Graph ngg : nextGeneration) {
				ngg.clearFitness();
			}
			Collections.sort(nextGeneration, new GraphFitnessComparator(HEALConstants.SortType.DESC));
			Collections.sort(generation, new GraphFitnessComparator(HEALConstants.SortType.DESC));
			if (generation.size() > generationAdded) {
				generation = generation.subList(0, generationAdded);
			}

			generation.addAll(nextGeneration.subList(0, generationBase));
			
			Collections.sort(generation, new GraphFitnessComparator(HEALConstants.SortType.DESC));
			//for (int ngri = 0; ngri < generationAdded; ngri++) {
			while (generation.size() < 100) {
				Graph newGraph = new Graph(graph.getMatrix(), graph.getChromaticNumber(), generation.get(0).getBestColoring(), graph.getInitialColors());
				
				generation.add(randomColoring.color(newGraph));
			}
			
			System.out.println("velkost populacie: " + generation.size());
			
			System.out.println("finding coloring : " + generation.get(0).getBestColoring());
			
			System.out.println("best individual fitness: " + generation.get(0).getFitness());
			System.out.println("best individual colors: " + generation.get(0).getColors(null).size());
			List<Edge> conflictedEdges = generation.get(0).getConflitedEdges();
			System.out.println("best individual conflicted edges: " + conflictedEdges.size());
			System.out.println("best individual conflicted vertices: " + generation.get(0).getConflictedVertices(conflictedEdges).size());
			nextGeneration = new ArrayList<Graph>();
			if (generation.get(0).getFitness() >= 1.0) {
				bestIndividual = new Graph(generation.get(0));
				int colors = bestIndividual.getColors(null).size();
				
				if (colors == bestIndividual.getChromaticNumber()) {
					return bestIndividual;
				}
			
				System.out.println("nastavujem best coloring na " + (colors - 1));
				for (Graph g : generation) {
					g.setBestColoring(colors - 1);
					// TODO clear fitness?
					j = 0;
				}
			}
			List<Graph> toCross = new ArrayList<Graph>();
			int k = 0;
			for (Graph g : generation) {
				k++;
				//Collections.sort(g.getVertices(), new VertexConflictsComparator(HEALConstants.SortType.DESC));
				Graph zaloznyGraf = new Graph(g);
				nextGeneration.add(g);
				nextGeneration.add(zaloznyGraf);
//				System.out.println("fitness before original: " + g.getFitness());
//				System.out.println("fitness before zalozny: " + zaloznyGraf.getFitness());

				if (toCross.size() == 1 && k == generation.size()) {
					this.cross(toCross.get(0), g);
					toCross = new ArrayList<Graph>();
				} else if (toCross.size() == 0 && k == generation.size()) {
					this.mutation(g);
				} else {
					Random rand = new Random();
					double random = rand.nextDouble();
					if (random < PERMUTATION_PROBABILITY) {
						this.permutation(g);
					} else {
						if (toCross.size() == 0) {
							toCross.add(g);
						} else {
							this.cross(toCross.get(0), g);
							toCross = new ArrayList<Graph>();
						}
					}
				}
				this.mutation(g);
//				System.out.println("fitness after original: " + g.getFitness());
//				System.out.println("fitness after zalozny: " + zaloznyGraf.getFitness());
			}
		}
		for (Graph ngg : nextGeneration) {
			ngg.clearFitness();
		}
		Collections.sort(nextGeneration, new GraphFitnessComparator(HEALConstants.SortType.DESC));
		if (bestIndividual == null) {
			bestIndividual = nextGeneration.get(0);
			
			// ako to ze toto tu vratilo zle ofarbeny graf??? riesenie - mozno treba pregenerovat conflicts count - cez fitness
			
			if (!bestIndividual.isWellColored()) {
				int toBeRepaired = 0;
				for (Vertex vertex : bestIndividual.getVertices()) {
					if (vertex.getConflictsCount() > 0) {
						vertex.setColor(0);
						toBeRepaired++;
					}
				}
				System.out.println("To be repaired: " + toBeRepaired + " - total: " + bestIndividual.getVertices().size());
				brelaz = new BrelazAlgorithm();
				bestIndividual = brelaz.color(bestIndividual);
				if (!bestIndividual.isWellColored()) {
					System.out.println("ako to ze nie je dobre ofarbeny?");
				}
			}
		}
		return bestIndividual;
	}
	
	private void clearColors(Vertex vertex, int distance) {
		if (distance > 0) {
			for (Vertex neighbour : vertex.getNeighbours()) {
				if (neighbour.getColor() != 0) {
					neighbour.setColor(0);
					this.clearColors(neighbour, distance - 1);
				}
			}
		}
	}
	
	private void mutation(Graph graph) {
		int maxColor = graph.getBestColoring();
		int newColor = 0;
		Random rand = new Random();
		double random;
		// zoradit vrcholy podla poctu conflictov, postupne menit farbu a preratavat konflikty u susedov daneho vrcholu
		Collections.sort(graph.getVertices(), vertexConflictsComparator);
		for (Vertex vertex : graph.getVertices()) {
			random = rand.nextDouble();
			newColor = graph.getMinimalFreeColor(vertex.getNeighbours(), null);
			if ((vertex.getConflictsCount() > 0 || vertex.getColor() > maxColor) && random < CONFLICTED_VERTICES_MUTATION_PROBABILITY) {
			//	System.out.println(newColor);
				if (newColor > maxColor) {
					this.clearColors(vertex, 1);
					vertex.setColor(0);
				} else {
					vertex.setColor(newColor);
				}
			}  else if (vertex.getConflictsCount() == 0 && random < NON_CONFLICTED_VERTICES_MUTATION_PROBABILITY) {
				this.clearColors(vertex, 1);
				vertex.setColor(0);
			}
		}

		
//		int count = 0;
//		for (Vertex vertex : graph.getVertices()) {
//			random = rand.nextDouble();
//			if (vertex.getConflictsCount() > 0) {
//				count++;
//				if (random < CONFLICTED_VERTICES_MUTATION_PROBABILITY) {
//					vertex.setColor(0);
//				}
//			} else {
//				if (random < NON_CONFLICTED_VERTICES_MUTATION_PROBABILITY) {
//					vertex.setColor(0);
//				}
//			}
//		}
	//	graph.printColors();
		// TODO nemozem dovolit brelazovi aby pouzil viac farieb ako je max
		random = rand.nextDouble();
		AbstractAlgorithm algorithm = null;
		if (random < 0) {
			algorithm = new BrelazAlgorithm();
		} else {
			//algorithm = new RandomColoringAlgorithm();
			algorithm = new TabuColoringAlgorithm();
		}
		
		if (algorithm != null) {
			algorithm.color(graph);
			
			if (graph.isWellColored()) {
				MinimizeColorAlgorithm alg = new MinimizeColorAlgorithm();
				alg.color(graph);
			}
		}
		
// TODO : skusit rychly min first ci ako sa to volalo
		
		// este nejaky musim najst co to tiez dobre dofarbuje
		
		// TODO : spravit algoritmus, ktory si pamata predchadzajucu farbu a vidi sucasnu farbu a zafarbi vrchol inak ako tymito dvoma farbami
		
//		graph.randomColoring();
//		System.out.println(graph.getFitness());
	}
	
	private void permutation(Graph graph) {
//		System.out.println("permutation");
//		System.out.println(graph.getFitness());
		Random rand = new Random();
		int randomVertex1 = rand.nextInt(graph.getVertices().size()) + 1;
		int randomVertex2 = rand.nextInt(graph.getVertices().size()) + 1;
		List<Vertex> permutedVertices = new ArrayList<Vertex>();
		for (Vertex vertex : graph.getVertices()) {
			if (vertex.getId() == randomVertex1) {
				permutedVertices.add(vertex);
			}
			if (vertex.getId() == randomVertex2) {
				permutedVertices.add(vertex);
			}
			if (permutedVertices.size() == 2) {
				break;
			}
		}
		
		if (permutedVertices.size() == 2) {
			Vertex v1 = permutedVertices.get(0);
			Vertex v2 = permutedVertices.get(1);
			
			int color = v1.getColor();
			v1.setColor(v2.getColor());
			v2.setColor(color);
		}
//		System.out.println(graph.getFitness());
	}
	
	private void cross(Graph graph1, Graph graph2) {
//		System.out.println("crossing");
//		System.out.println(graph1.getFitness());
//		System.out.println(graph2.getFitness());
		int count = (int) Math.floor(graph1.getVertices().size() * CROSS_PORTION);
		
		Random rand = new Random();
		for (int i = 0; i < count; i++) {
			int randomVertex1 = rand.nextInt(graph1.getVertices().size()) + 1;
			int randomVertex2 = rand.nextInt(graph1.getVertices().size()) + 1;
			List<Vertex> crossedVertices = new ArrayList<Vertex>();
			for (Vertex vertex : graph1.getVertices()) {
				if (vertex.getId() == randomVertex1) {
					crossedVertices.add(vertex);
				}
			}
			for (Vertex vertex : graph2.getVertices()) {
				if (vertex.getId() == randomVertex2) {
					crossedVertices.add(vertex);
				}			
			}
			
			if (crossedVertices.size() == 2) {
				Vertex v1 = crossedVertices.get(0);
				Vertex v2 = crossedVertices.get(1);
				
				int color = v1.getColor();
				v1.setColor(v2.getColor());
				v2.setColor(color);
			}
		}
//		System.out.println(graph1.getFitness());
//		System.out.println(graph2.getFitness());
	}
}